// https://leetcode.cn/problems/spiral-matrix/description/?envType=study-plan-v2&envId=top-100-liked



class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        vector<int> ret;
        if (matrix.empty())
            return ret;
        int col = matrix[0].size();
        int row = matrix.size();
        vector<vector<int>> flag(row, vector<int>(col, 0));
        int count = col * row;
        int n = 0, m = 0;
        int x = dx[n], y = dy[m];
        int i = 0, j = 0, k = 0;
        while (k < count) {
            ret.push_back(matrix[i][j]);
            flag[i][j] = 1;
            k++;
            i += x;
            j += y;
            if (i >= row || i < 0 || j >= col || j < 0 || flag[i][j] == 1) {
                i -= x;
                j -= y;
                n = (n + 1) % 4;
                m = (m + 1) % 4;
                x = dx[n];
                y = dy[m];
                i += x;
                j += y;
            }
        }
        return ret;
    }
};

